HyperLib 1997 Winter

home *** CD-ROM | disk | FTP | other *** search

/ HyperLib 1997 Winter - Disc 1 / HYPERLIB-1997-Winter-CD1.ISO.7z / HYPERLIB-1997-Winter-CD1.ISO / オンラインウェア / PRG / PL 2.0 SupplementDoc Folder.sit / PL 2.0 SupplementDoc Folder / Documentation / Chapter 14. Sequences < prev next >

Wrap

Text File | 1995-03-27 | 52KB | 1,190 lines

Common Lisp the Language, 2nd Edition ------------------------------------------------------------------------------- 14. Sequences The type sequence encompasses both lists and vectors (one-dimensional arrays). While these are different data structures with different structural properties leading to different algorithmic uses, they do have a common property: each contains an ordered set of elements. Note that nil is considered to be a sequence of length zero. Some operations are useful on both lists and arrays because they deal with ordered sets of elements. One may ask the number of elements, reverse the ordering, extract a subsequence, and so on. For such purposes Common Lisp provides a set of generic functions on sequences. [change_begin] Note that this remark, predating the design of the Common Lisp Object System, uses the term ``generic'' in a generic sense, and not necessarily in the technical sense used by CLOS (see chapter 2). [change_end] elt reverse map remove length nreverse some remove-duplicates subseq concatenate every delete copy-seq position notany delete-duplicates fill find notevery substitute replace sort reduce nsubstitute count merge search mismatch Some of these operations come in more than one version. Such versions are indicated by adding a suffix (or occasionally a prefix) to the basic name of the operation. In addition, many operations accept one or more optional keyword arguments that can modify the operation in various ways. If the operation requires testing sequence elements according to some criterion, then the criterion may be specified in one of two ways. The basic operation accepts an item, and elements are tested for being eql to that item. (A test other than eql can be specified by the :test or :test-not keyword. It is an error to use both of these keywords in the same call.) The variants formed by adding -if and -if-not to the basic operation name do not take an item, but instead a one-argument predicate, and elements are tested for satisfying or not satisfying the predicate. As an example, (remove item sequence) returns a copy of sequence from which all elements eql to item have been removed; (remove item sequence :test #'equal) returns a copy of sequence from which all elements equal to item have been removed; (remove-if #'numberp sequence) returns a copy of sequence from which all numbers have been removed. If an operation tests elements of a sequence in any manner, the keyword argument :key, if not nil, should be a function of one argument that will extract from an element the part to be tested in place of the whole element. For example, the effect of the MacLisp expression (assq item seq) could be obtained by (find item sequence :test #'eq :key #'car) This searches for the first element of sequence whose car is eq to item. [change_begin] X3J13 voted in June 1988 (FUNCTION-TYPE) to allow the :key function to be only of type symbol or function; a lambda-expression is no longer acceptable as a functional argument. One must use the function special form or the abbreviation #' before a lambda-expression that appears as an explicit argument form. [change_end] For some operations it can be useful to specify the direction in which the sequence is conceptually processed. In this case the basic operation normally processes the sequence in the forward direction, and processing in the reverse direction is indicated by a non-nil value for the keyword argument :from-end. (The processing order specified by the :from-end is purely conceptual. Depending on the object to be processed and on the implementation, the actual processing order may be different. For this reason a user-supplied test function should be free of side effects.) Many operations allow the specification of a subsequence to be operated upon. Such operations have keyword arguments called :start and :end. These arguments should be integer indices into the sequence, with startend (it is an error if start>end). They indicate the subsequence starting with and including element start and up to but excluding element end. The length of the subsequence is therefore end-start. If start is omitted, it defaults to zero; and if end is omitted or nil, it defaults to the length of the sequence. Therefore if both start and end are omitted, the entire sequence is processed by default. For the most part, subsequence specification is permitted purely for the sake of efficiency; one could simply call subseq instead to extract the subsequence before operating on it. Note, however, that operations that calculate indices return indices into the original sequence, not into the subsequence: (position #¥b "foobar" :start 2 :end 5) => 3 (position #¥b (subseq "foobar" 2 5)) => 1 If two sequences are involved, then the keyword arguments :start1, :end1, :start2, and :end2 are used to specify separate subsequences for each sequence. [change_begin] X3J13 voted in June 1988 (SUBSEQ-OUT-OF-BOUNDS) (and further clarification was voted in January 1989 (RANGE-OF-START-AND-END-PARAMETERS) ) to specify that these rules apply not only to all built-in functions that have keyword parameters named :start, :start1, :start2, :end, :end1, or :end2 but also to functions such as subseq that take required or optional parameters that are documented as being named start or end. * A ``start'' argument must always be a non-negative integer and defaults to zero if not supplied; it is not permissible to pass nil as a ``start'' argument. * An ``end'' argument must be either a non-negative integer or nil (which indicates the end of the sequence) and defaults to nil if not supplied; therefore supplying nil is equivalent to not supplying such an argument. * If the ``end'' argument is an integer, it must be no greater than the active length of the corresponding sequence (as returned by the function length). * The default value for the ``end'' argument is the active length of the corresponding sequence. * The ``start'' value (after defaulting, if necessary) must not be greater than the corresponding ``end'' value (after defaulting, if necessary). This may be summarized as follows. Let x be the sequence within which indices are to be considered. Let s be the ``start'' argument for that sequence of any standard function, whether explicitly specified or defaulted, through omission, to zero. Let e be the ``end'' argument for that sequence of any standard function, whether explicitly specified or defaulted, through omission or an explicitly passed nil value, to the active length of x, as returned by length. Then it is an error if the test (<= 0 s e (length x)) is not true. [change_end] For some functions, notably remove and delete, the keyword argument :count is used to specify how many occurrences of the item should be affected. If this is nil or is not supplied, all matching items are affected. In the following function descriptions, an element x of a sequence ``satisfies the test'' if any of the following holds: * A basic function was called, testfn was specified by the keyword :test, and (funcall testfn item (keyfn x)) is true. * A basic function was called, testfn was specified by the keyword :test-not, and (funcall testfn item (keyfn x)) is false. * An -if function was called, and (funcall predicate (keyfn x)) is true. * An -if-not function was called, and (funcall predicate (keyfn x)) is false. In each case keyfn is the value of the :key keyword argument (the default being the identity function). See, for example, remove. In the following function descriptions, two elements x and y taken from sequences ``match'' if either of the following holds: * testfn was specified by the keyword :test, and (funcall testfn (keyfn x) (keyfn y)) is true. * testfn was specified by the keyword :test-not, and (funcall testfn (keyfn x) (keyfn y)) is false. See, for example, search. [change_begin] X3J13 voted in June 1988 (FUNCTION-TYPE) to allow the testfn or predicate to be only of type symbol or function; a lambda-expression is no longer acceptable as a functional argument. One must use the function special form or the abbreviation #' before a lambda-expression that appears as an explicit argument form. [change_end] You may depend on the order in which arguments are given to testfn; this permits the use of non-commutative test functions in a predictable manner. The order of the arguments to testfn corresponds to the order in which those arguments (or the sequences containing those arguments) were given to the sequence function in question. If a sequence function gives two elements from the same sequence argument to testfn, they are given in the same order in which they appear in the sequence. Whenever a sequence function must construct and return a new vector, it always returns a simple vector (see section 2.5). Similarly, any strings constructed will be simple strings. [change_begin] X3J13 voted in January 1989 (TEST-NOT-IF-NOT) to deprecate the use of :test-not keyword arguments and -if-not functions. This means that these features are very likely to be retained in the forthcoming standard but are regarded as candidates for removal in a future revision of the ANSI standard. X3J13 also voted in January 1989 (FUNCTION-COMPOSITION) to add the complement function, intended to reduce or eliminate the need for these deprecated features. Time will tell. I note that many features in Fortran have been deprecated but very few indeed have actually been removed or altered incompatibly. [Function] complement fn Returns a function whose value is the same as that of not applied to the result of applying the function fn to the same arguments. One could define complement as follows: (defun complement (fn) #'(lambda (&rest arguments) (not (apply fn arguments)))) One intended use of complement is to supplant the use of :test-not arguments and -if-not functions. (remove-if-not #'virtuous senators) == (remove-if (complement #'virtuous) senators) (remove-duplicates telephone-book :test-not #'mismatch) == (remove-duplicates telephone-book :test (complement #'mismatch)) [change_end] ------------------------------------------------------------------------------- * Simple Sequence Functions * Concatenating, Mapping, and Reducing Sequences * Modifying Sequences * Searching Sequences for Items * Sorting and Merging ------------------------------------------------------------------------------- 14.1. Simple Sequence Functions Most of the following functions perform simple operations on a single sequence; make-sequence constructs a new sequence. [Function] elt sequence index This returns the element of sequence specified by index, which must be a non-negative integer less than the length of the sequence as returned by length. The first element of a sequence has index 0. (Note that elt observes the fill pointer in those vectors that have fill pointers. The array-specific function aref may be used to access vector elements that are beyond the vector's fill pointer.) setf may be used with elt to destructively replace a sequence element with a new value. [Function] subseq sequence start &optional end This returns the subsequence of sequence specified by start and end. subseq always allocates a new sequence for a result; it never shares storage with an old sequence. The result subsequence is always of the same type as the argument sequence. setf may be used with subseq to destructively replace a subsequence with a sequence of new values; see also replace. [Function] copy-seq sequence A copy is made of the argument sequence; the result is equalp to the argument but not eq to it. (copy-seq x) == (subseq x 0) but the name copy-seq is more perspicuous when applicable. [Function] length sequence The number of elements in sequence is returned as a non-negative integer. If the sequence is a vector with a fill pointer, the ``active length'' as specified by the fill pointer is returned (see section 17.5). [Function] reverse sequence The result is a new sequence of the same kind as sequence, containing the same elements but in reverse order. The argument is not modified. [Function] nreverse sequence The result is a sequence containing the same elements as sequence but in reverse order. The argument may be destroyed and re-used to produce the result. The result may or may not be eq to the argument, so it is usually wise to say something like (setq x (nreverse x)), because simply (nreverse x) is not guaranteed to leave a reversed value in x. [change_begin] X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations. When the sequence is a list, nreverse is permitted to perform a setf on any part, car or cdr, of the top-level list structure of that list. When the sequence is an array, nreverse is permitted to re-order the elements of the given array in order to produce the resulting array. [change_end] [Function] make-sequence type size &key :initial-element This returns a sequence of type type and of length size, each of whose elements has been initialized to the :initial-element argument. If specified, the :initial-element argument must be an object that can be an element of a sequence of type type. For example: (make-sequence '(vector double-float) 100 :initial-element 1d0) If an :initial-element argument is not specified, then the sequence will be initialized in an implementation-dependent way. [change_begin] X3J13 voted in January 1989 (ARGUMENTS-UNDERSPECIFIED) to clarify that the type argument must be a type specifier, and the size argument must be a non-negative integer less than the value of array-dimension-limit. X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH) to specify that make-sequence should signal an error if the sequence type specifies the number of elements and the size argument is different. X3J13 voted in March 1989 (CHARACTER-PROPOSAL) to specify that if type is string, the result is the same as if make-string had been called with the same size and :initial-element arguments. [change_end] ------------------------------------------------------------------------------- 14.2. Concatenating, Mapping, and Reducing Sequences The functions in this section each operate on an arbitrary number of sequences except for reduce, which is included here because of its conceptual relationship to the mapping functions. [Function] concatenate result-type &rest sequences The result is a new sequence that contains all the elements of all the sequences in order. All of the sequences are copied from; the result does not share any structure with any of the argument sequences (in this concatenate differs from append). The type of the result is specified by result-type, which must be a subtype of sequence, as for the function coerce. It must be possible for every element of the argument sequences to be an element of a sequence of type result-type. If only one sequence argument is provided and it has the type specified by result-type, concatenate is required to copy the argument rather than simply returning it. If a copy is not required, but only possibly type conversion, then the coerce function may be appropriate. [change_begin] X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH) to specify that concatenate should signal an error if the sequence type specifies the number of elements and the sum of the argument lengths is different. [change_end] [Function] map result-type function sequence &rest more-sequences The function must take as many arguments as there are sequences provided; at least one sequence must be provided. The result of map is a sequence such that element j is the result of applying function to element j of each of the argument sequences. The result sequence is as long as the shortest of the input sequences. If the function has side effects, it can count on being called first on all the elements numbered 0, then on all those numbered 1, and so on. The type of the result sequence is specified by the argument result-type (which must be a subtype of the type sequence), as for the function coerce. In addition, one may specify nil for the result type, meaning that no result sequence is to be produced; in this case the function is invoked only for effect, and map returns nil. This gives an effect similar to that of mapc. [change_begin] X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH) to specify that map should signal an error if the sequence type specifies the number of elements and the minimum of the argument lengths is different. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] ------------------------------------------------------------------------------- Compatibility note: In MacLisp, Lisp Machine Lisp, Interlisp, and indeed even Lisp 1.5, the function map has always meant a non-value-returning version. However, standard computer science literature, including in particular the recent wave of papers on ``functional programming,'' have come to use map to mean what in the past Lisp implementations have called mapcar. To simplify things henceforth, Common Lisp follows current usage, and what was formerly called map is named mapl in Common Lisp. ------------------------------------------------------------------------------- For example: (map 'list #'- '(1 2 3 4)) => (-1 -2 -3 -4) (map 'string #'(lambda (x) (if (oddp x) #¥1 #¥0)) '(1 2 3 4)) => "1010" [change_begin] [Function] map-into result-sequence function &rest sequences X3J13 voted in June 1989 (MAP-INTO) to add the function map-into. It destructively modifies the result-sequence to contain the results of applying function to corresponding elements of the argument sequences in turn; it then returns result-sequence. The arguments result-sequence and each element of sequences can each be either a list or a vector (one-dimensional array). The function must accept at least as many arguments as the number of argument sequences supplied to map-into. If result-sequence and the other argument sequences are not all the same length, the iteration terminates when the shortest sequence is exhausted. If result-sequence is a vector with a fill pointer, the fill pointer is ignored when deciding how many iterations to perform, and afterwards the fill pointer is set to the number of times the function was applied. If the function has side effects, it can count on being called first on all the elements numbered 0, then on all those numbered 1, and so on. If result-sequence is longer than the shortest element of sequences, extra elements at the end of result-sequence are unchanged. The function map-into differs from map in that it modifies an existing sequence rather than creating a new one. In addition, map-into can be called with only two arguments (result-sequence and function), while map requires at least three arguments. If result-sequence is nil, map-into immediately returns nil, because nil is a sequence of length zero. [change_end] [Function] some predicate sequence &rest more-sequences every predicate sequence &rest more-sequences notany predicate sequence &rest more-sequences notevery predicate sequence &rest more-sequences These are all predicates. The predicate must take as many arguments as there are sequences provided. The predicate is first applied to the elements with index 0 in each of the sequences, and possibly then to the elements with index 1, and so on, until a termination criterion is met or the end of the shortest of the sequences is reached. If the predicate has side effects, it can count on being called first on all the elements numbered 0, then on all those numbered 1, and so on. some returns as soon as any invocation of predicate returns a non-nil value; some returns that value. If the end of a sequence is reached, some returns nil. Thus, considered as a predicate, it is true if some invocation of predicate is true. every returns nil as soon as any invocation of predicate returns nil. If the end of a sequence is reached, every returns a non-nil value. Thus, considered as a predicate, it is true if every invocation of predicate is true. notany returns nil as soon as any invocation of predicate returns a non-nil value. If the end of a sequence is reached, notany returns a non-nil value. Thus, considered as a predicate, it is true if no invocation of predicate is true. notevery returns a non-nil value as soon as any invocation of predicate returns nil. If the end of a sequence is reached, notevery returns nil. Thus, considered as a predicate, it is true if not every invocation of predicate is true. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] ------------------------------------------------------------------------------- Compatibility note: The order of the arguments here is not compatible with Interlisp and Lisp Machine Lisp. This is to stress the similarity of these functions to map. The functions are therefore extended here to functions of more than one argument, and to multiple sequences. ------------------------------------------------------------------------------- [Function] reduce function sequence &key :from-end :start :end :initial-value The reduce function combines all the elements of a sequence using a binary operation; for example, using + one can add up all the elements. The specified subsequence of the sequence is combined or ``reduced'' using the function, which must accept two arguments. The reduction is left-associative, unless the :from-end argument is true (it defaults to nil), in which case it is right-associative. If an :initial-value argument is given, it is logically placed before the subsequence (after it if :from-end is true) and included in the reduction operation. If the specified subsequence contains exactly one element and the keyword argument :initial-value is not given, then that element is returned and the function is not called. If the specified subsequence is empty and an :initial-value is given, then the :initial-value is returned and the function is not called. If the specified subsequence is empty and no :initial-value is given, then the function is called with zero arguments, and reduce returns whatever the function does. (This is the only case where the function is called with other than two arguments.) (reduce #'+ '(1 2 3 4)) => 10 (reduce #'- '(1 2 3 4)) == (- (- (- 1 2) 3) 4) => -8 (reduce #'- '(1 2 3 4) :from-end t) ;Alternating sum == (- 1 (- 2 (- 3 4))) => -2 (reduce #'+ '()) => 0 (reduce #'+ '(3)) => 3 (reduce #'+ '(foo)) => foo (reduce #'list '(1 2 3 4)) => (((1 2) 3) 4) (reduce #'list '(1 2 3 4) :from-end t) => (1 (2 (3 4))) (reduce #'list '(1 2 3 4) :initial-value 'foo) => ((((foo 1) 2) 3) 4) (reduce #'list '(1 2 3 4) :from-end t :initial-value 'foo) => (1 (2 (3 (4 foo)))) If the function produces side effects, the order of the calls to the function can be correctly predicted from the reduction ordering demonstrated above. [change_begin] The name ``reduce'' for this function is borrowed from APL. X3J13 voted in March 1988 (REDUCE-ARGUMENT-EXTRACTION) to extend the reduce function to take an additional keyword argument named :key. As usual, this argument defaults to the identity function. The value of this argument must be a function that accepts at least one argument. This function is applied once to each element of the sequence that is to participate in the reduction operation, in the order implied by the :from-end argument; the values returned by this function are combined by the reduction function. However, the :key function is not applied to the :initial-value argument (if any). X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] ------------------------------------------------------------------------------- 14.3. Modifying Sequences Each of these functions alters the contents of a sequence or produces an altered copy of a given sequence. [Function] fill sequence item &key :start :end The sequence is destructively modified by replacing each element of the subsequence specified by the :start and :end parameters with the item. The item may be any Lisp object but must be a suitable element for the sequence. The item is stored into all specified components of the sequence, beginning at the one specified by the :start index (which defaults to zero), up to but not including the one specified by the :end index (which defaults to the length of the sequence). fill returns the modified sequence. For example: (setq x (vector 'a 'b 'c 'd 'e)) => #(a b c d e) (fill x 'z :start 1 :end 3) => #(a z z d e) and now x => #(a z z d e) (fill x 'p) => #(p p p p p) and now x => #(p p p p p) [Function] replace sequence1 sequence2 &key :start1 :end1 :start2 :end2 The sequence sequence1 is destructively modified by copying successive elements into it from sequence2. The elements of sequence2 must be of a type that may be stored into sequence1. The subsequence of sequence2 specified by :start2 and :end2 is copied into the subsequence of sequence1 specified by :start1 and :end1. (The arguments :start1 and :start2 default to zero. The arguments :end1 and :end2 default to nil, meaning the end of the appropriate sequence.) If these subsequences are not of the same length, then the shorter length determines how many elements are copied; the extra elements near the end of the longer subsequence are not involved in the operation. The number of elements copied may be expressed as: (min (- end1 start1) (- end2 start2)) The value returned by replace is the modified sequence1. If sequence1 and sequence2 are the same (eq) object and the region being modified overlaps the region being copied from, then it is as if the entire source region were copied to another place and only then copied back into the target region. However, if sequence1 and sequence2 are not the same, but the region being modified overlaps the region being copied from (perhaps because of shared list structure or displaced arrays), then after the replace operation the subsequence of sequence1 being modified will have unpredictable contents. [Function] remove item sequence &key :from-end :test :test-not :start :end :count :key remove-if predicate sequence &key :from-end :start :end :count :key remove-if-not predicate sequence &key :from-end :start :end :count :key The result is a sequence of the same kind as the argument sequence that has the same elements except that those in the subsequence delimited by :start and :end and satisfying the test (see above) have been removed. This is a non-destructive operation; the result is a copy of the input sequence, save that some elements are not copied. Elements not removed occur in the same order in the result as they did in the argument. The :count argument, if supplied, limits the number of elements removed; if more than :count elements satisfy the test, then of these elements only the leftmost are removed, as many as specified by :count. [change_begin] X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD) to clarify that the :count argument must be either nil or an integer, and that supplying a negative integer produces the same behavior as supplying zero. [change_end] A non-nil :from-end specification matters only when the :count argument is provided; in that case only the rightmost :count elements satisfying the test are removed. For example: (remove 4 '(1 2 4 1 3 4 5)) => (1 2 1 3 5) (remove 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 1 3 4 5) (remove 4 '(1 2 4 1 3 4 5) :count 1 :from-end t) => (1 2 4 1 3 5) (remove 3 '(1 2 4 1 3 4 5) :test #'>) => (4 3 4 5) (remove-if #'oddp '(1 2 4 1 3 4 5)) => (2 4 4) (remove-if #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t) => (1 2 4 1 3 5) The result of remove may share with the argument sequence; a list result may share a tail with an input list, and the result may be eq to the input sequence if no elements need to be removed. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] [Function] delete item sequence &key :from-end :test :test-not :start :end :count :key delete-if predicate sequence &key :from-end :start :end :count :key delete-if-not predicate sequence &key :from-end :start :end :count :key This is the destructive counterpart to remove. The result is a sequence of the same kind as the argument sequence that has the same elements except that those in the subsequence delimited by :start and :end and satisfying the test (see above) have been deleted. This is a destructive operation. The argument sequence may be destroyed and used to construct the result; however, the result may or may not be eq to sequence. Elements not deleted occur in the same order in the result as they did in the argument. The :count argument, if supplied, limits the number of elements deleted; if more than :count elements satisfy the test, then of these elements only the leftmost are deleted, as many as specified by :count. [change_begin] X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD) to clarify that the :count argument must be either nil or an integer, and that supplying a negative integer produces the same behavior as supplying zero. [change_end] A non-nil :from-end specification matters only when the :count argument is provided; in that case only the rightmost :count elements satisfying the test are deleted. For example: (delete 4 '(1 2 4 1 3 4 5)) => (1 2 1 3 5) (delete 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 1 3 4 5) (delete 4 '(1 2 4 1 3 4 5) :count 1 :from-end t) => (1 2 4 1 3 5) (delete 3 '(1 2 4 1 3 4 5) :test #'>) => (4 3 4 5) (delete-if #'oddp '(1 2 4 1 3 4 5)) => (2 4 4) (delete-if #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t) => (1 2 4 1 3 5) [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations. When the sequence is a list, delete is permitted to perform a setf on any part, car or cdr, of the top-level list structure of that list. When the sequence is an array, delete is permitted to alter the dimensions of the given array and to slide some of its elements into new positions without permuting them in order to produce the resulting array. Furthermore, (delete-if predicate sequence ...) is required to behave exactly like (delete nil sequence :test #'(lambda (unused item) (declare (ignore unused)) (funcall predicate item)) ...) [change_end] ------------------------------------------------------------------------------- Compatibility note: In MacLisp, the delete function uses an equal comparison rather than eql, which is the default test for delete in Common Lisp. Where in MacLisp one would write (delete x y), one must in Common Lisp write (delete x y :test #'equal) to get the completely identical effect. Similarly, one can get the precise effect, and no more, of the MacLisp (delq x y) by writing in Common Lisp (delete x y :test #'eq). ------------------------------------------------------------------------------- [Function] remove-duplicates sequence &key :from-end :test :test-not :start :end :key delete-duplicates sequence &key :from-end :test :test-not :start :end :key The elements of sequence are compared pairwise, and if any two match, then the one occurring earlier in the sequence is discarded (but if the :from-end argument is true, then the one later in the sequence is discarded). The result is a sequence of the same kind as the argument sequence with enough elements removed so that no two of the remaining elements match. The order of the elements remaining in the result is the same as the order in which they appear in sequence. remove-duplicates is the non-destructive version of this operation. The result of remove-duplicates may share with the argument sequence; a list result may share a tail with an input list, and the result may be eq to the input sequence if no elements need to be removed. delete-duplicates may destroy the argument sequence. Some examples: (remove-duplicates '(a b c b d d e)) => (a c b d e) (remove-duplicates '(a b c b d d e) :from-end t) => (a b c d e) (remove-duplicates '((foo #¥a) (bar #¥%) (baz #¥A)) :test #'char-equal :key #'cadr) => ((bar #¥%) (baz #¥A)) (remove-duplicates '((foo #¥a) (bar #¥%) (baz #¥A)) :test #'char-equal :key #'cadr :from-end t) => ((foo #¥a) (bar #¥%)) These functions are useful for converting a sequence into a canonical form suitable for representing a set. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations. When the sequence is a list, delete-duplicates is permitted to perform a setf on any part, car or cdr, of the top-level list structure of that list. When the sequence is an array, delete-duplicates is permitted to alter the dimensions of the given array and to slide some of its elements into new positions without permuting them in order to produce the resulting array. [change_end] [Function] substitute newitem olditem sequence &key :from-end :test :test-not :start :end :count :key substitute-if newitem test sequence &key :from-end :start :end :count :key substitute-if-not newitem test sequence &key :from-end :start :end :count :key The result is a sequence of the same kind as the argument sequence that has the same elements except that those in the subsequence delimited by :start and :end and satisfying the test (see above) have been replaced by newitem. This is a non-destructive operation; the result is a copy of the input sequence, save that some elements are changed. The :count argument, if supplied, limits the number of elements altered; if more than :count elements satisfy the test, then of these elements only the leftmost are replaced, as many as specified by :count. [change_begin] X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD) to clarify that the :count argument must be either nil or an integer, and that supplying a negative integer produces the same behavior as supplying zero. [change_end] A non-nil :from-end specification matters only when the :count argument is provided; in that case only the rightmost :count elements satisfying the test are replaced. For example: (substitute 9 4 '(1 2 4 1 3 4 5)) => (1 2 9 1 3 9 5) (substitute 9 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 9 1 3 4 5) (substitute 9 4 '(1 2 4 1 3 4 5) :count 1 :from-end t) => (1 2 4 1 3 9 5) (substitute 9 3 '(1 2 4 1 3 4 5) :test #'>) => (9 9 4 9 3 4 5) (substitute-if 9 #'oddp '(1 2 4 1 3 4 5)) => (9 2 4 9 9 4 9) (substitute-if 9 #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t) => (1 2 4 1 3 9 5) The result of substitute may share with the argument sequence; a list result may share a tail with an input list, and the result may be eq to the input sequence if no elements need to be changed. See also subst, which performs substitutions throughout a tree. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] [Function] nsubstitute newitem olditem sequence &key :from-end :test :test-not :start :end :count :key nsubstitute-if newitem test sequence &key :from-end :start :end :count :key nsubstitute-if-not newitem test sequence &key :from-end :start :end :count :key This is the destructive counterpart to substitute. The result is a sequence of the same kind as the argument sequence that has the same elements except that those in the subsequence delimited by :start and :end and satisfying the test (see above) have been replaced by newitem. This is a destructive operation. The argument sequence may be destroyed and used to construct the result; however, the result may or may not be eq to sequence. See also nsubst, which performs destructive substitutions throughout a tree. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations. When the sequence is a list, nsubstitute or nsubstitute-if is required to perform a setf on any car of the top-level list structure of that list whose old contents must be replaced with newitem but is forbidden to perform a setf on any cdr of the list. When the sequence is an array, nsubstitute or nsubstitute-if is required to perform a setf on any element of the array whose old contents must be replaced with newitem. These functions, therefore, may successfully be used solely for effect, the caller discarding the returned value (though some programmers find this stylistically distasteful). [change_end] ------------------------------------------------------------------------------- 14.4. Searching Sequences for Items Each of these functions searches a sequence to locate one or more elements satisfying some test. [Function] find item sequence &key :from-end :test :test-not :start :end :key find-if predicate sequence &key :from-end :start :end :key find-if-not predicate sequence &key :from-end :start :end :key If the sequence contains an element satisfying the test, then the leftmost such element is returned; otherwise nil is returned. If :start and :end keyword arguments are given, only the specified subsequence of sequence is searched. If a non-nil :from-end keyword argument is specified, then the result is the rightmost element satisfying the test. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] [Function] position item sequence &key :from-end :test :test-not :start :end :key position-if predicate sequence &key :from-end :start :end :key position-if-not predicate sequence &key :from-end :start :end :key If the sequence contains an element satisfying the test, then the index within the sequence of the leftmost such element is returned as a non-negative integer; otherwise nil is returned. If :start and :end keyword arguments are given, only the specified subsequence of sequence is searched. However, the index returned is relative to the entire sequence, not to the subsequence. If a non-nil :from-end keyword argument is specified, then the result is the index of the rightmost element satisfying the test. (The index returned, however, is an index from the left-hand end, as usual.) [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. Here is a simple piece of code that uses several of the sequence functions, notably position-if and find-if, to process strings. Note one use of loop as well. (defun debug-palindrome (s) (flet ((match (x) (char-equal (first x) (third x)))) (let* ((pairs (loop for c across s for j from 0 when (alpha-char-p c) collect (list c j))) (quads (mapcar #'append pairs (reverse pairs))) (diffpos (position-if (complement #'match) quads))) (when diffpos (let* ((diff (elt quads diffpos)) (same (find-if #'match quads :start (+ diffpos 1)))) (if same (format nil "/~A/ (at ~D) is not the reverse of /~A/" (subseq s (second diff) (second same)) (second diff) (subseq s (+ (fourth same) 1) (+ (fourth diff) 1))) "This palindrome is completely messed up!")))))) Here is an example of its behavior. (setq panama ;A putative palindrome? "A man, a plan, a canoe, pasta, heros, rajahs, a coloratura, maps, waste, percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again (or a camel), a crepe, pins, Spam, a rut, a Rolo, cash, a jar, sore hats, a peon, a canal-Panama!") (debug-palindrome panama) => "/wast/ (at 73) is not the reverse of /, pins/" (replace panama "snipe" :start1 73) ;Repair it => "A man, a plan, a canoe, pasta, heros, rajahs, a coloratura, maps, snipe, percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again (or a camel), a crepe, pins, Spam, a rut, a Rolo, cash, a jar, sore hats, a peon, a canal-Panama!" (debug-palindrome panama) => nil ;Copacetic-a true palindrome (debug-palindrome "Rubber baby buggy bumpers") => "/Rubber / (at 0) is not the reverse of /umpers/" (debug-palindrome "Common Lisp: The Language") => "/Commo/ (at 0) is not the reverse of /guage/" (debug-palindrome "Complete mismatches are hard to find") => "/Complete mism/ (at 0) is not the reverse of /re hard to find/" (debug-palindrome "Waltz, nymph, for quick jigs vex Bud") => "This palindrome is completely messed up!" (debug-palindrome "Doc, note: I dissent. A fast never prevents a fatness. I diet on cod.") =>nil ;Another winner (debug-palindrome "Top step's pup's pet spot") => nil [change_end] [Function] count item sequence &key :from-end :test :test-not :start :end :key count-if predicate sequence &key :from-end :start :end :key count-if-not predicate sequence &key :from-end :start :end :key The result is always a non-negative integer, the number of elements in the specified subsequence of sequence satisfying the test. The :from-end argument does not affect the result returned; it is accepted purely for compatibility with other sequence functions. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] [Function] mismatch sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2 The specified subsequences of sequence1 and sequence2 are compared element-wise. If they are of equal length and match in every element, the result is nil. Otherwise, the result is a non-negative integer. This result is the index within sequence1 of the leftmost position at which the two subsequences fail to match; or, if one subsequence is shorter than and a matching prefix of the other, the result is the index relative to sequence1 beyond the last position tested. If a non-nil :from-end keyword argument is given, then one plus the index of the rightmost position in which the sequences differ is returned. In effect, the (sub)sequences are aligned at their right-hand ends; then, the last elements are compared, the penultimate elements, and so on. The index returned is again an index relative to sequence1. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] [Function] search sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2 A search is conducted for a subsequence of sequence2 that element-wise matches sequence1. If there is no such subsequence, the result is nil; if there is, the result is the index into sequence2 of the leftmost element of the leftmost such matching subsequence. If a non-nil :from-end keyword argument is given, the index of the leftmost element of the rightmost matching subsequence is returned. The implementation may choose to search the sequence in any order; there is no guarantee on the number of times the test is made. For example, search with a non-nil :from-end argument might actually search a list from left to right instead of from right to left (but in either case would return the rightmost matching subsequence, of course). Therefore it is a good idea for a user-supplied predicate to be free of side effects. [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] ------------------------------------------------------------------------------- 14.5. Sorting and Merging These functions may destructively modify argument sequences in order to put a sequence into sorted order or to merge two already sorted sequences. [Function] sort sequence predicate &key :key stable-sort sequence predicate &key :key The sequence is destructively sorted according to an order determined by the predicate. The predicate should take two arguments, and return non-nil if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the predicate should return nil. The sort function determines the relationship between two elements by giving keys extracted from the elements to the predicate. The :key argument, when applied to an element, should return the key for that element. The :key argument defaults to the identity function, thereby making the element itself be the key. The :key function should not have any side effects. A useful example of a :key function would be a component selector function for a defstruct structure, used in sorting a sequence of structures. (sort a p :key s) == (sort a #'(lambda (x y) (p (s x) (s y)))) While the above two expressions are equivalent, the first may be more efficient in some implementations for certain types of arguments. For example, an implementation may choose to apply s to each item just once, putting the resulting keys into a separate table, and then sort the parallel tables, as opposed to applying s to an item every time just before applying the predicate. If the :key and predicate functions always return, then the sorting operation will always terminate, producing a sequence containing the same elements as the original sequence (that is, the result is a permutation of sequence). This is guaranteed even if the predicate does not really consistently represent a total order (in which case the elements will be scrambled in some unpredictable way, but no element will be lost). If the :key function consistently returns meaningful keys, and the predicate does reflect some total ordering criterion on those keys, then the elements of the result sequence will be properly sorted according to that ordering. The sorting operation performed by sort is not guaranteed stable. Elements considered equal by the predicate may or may not stay in their original order. (The predicate is assumed to consider two elements x and y to be equal if (funcall predicate x y) and (funcall predicate y x) are both false.) The function stable-sort guarantees stability but may be slower than sort in some situations. The sorting operation may be destructive in all cases. In the case of an array argument, this is accomplished by permuting the elements in place. In the case of a list, the list is destructively reordered in the same manner as for nreverse. Thus if the argument should not be destroyed, the user must sort a copy of the argument. Should execution of the :key function or the predicate cause an error, the state of the list or array being sorted is undefined. However, if the error is corrected, the sort will, of course, proceed correctly. Note that since sorting requires many comparisons, and thus many calls to the predicate, sorting will be much faster if the predicate is a compiled function rather than interpreted. An example: (setq foovector (sort foovector #'string-lessp :key #'car)) If foovector contained these items before the sort ("Tokens" "The Lion Sleeps Tonight") ("Carpenters" "Close to You") ("Rolling Stones" "Brown Sugar") ("Beach Boys" "I Get Around") ("Mozart" "Eine Kleine Nachtmusik" (K 525)) ("Beatles" "I Want to Hold Your Hand") then after the sort foovector would contain ("Beach Boys" "I Get Around") ("Beatles" "I Want to Hold Your Hand") ("Carpenters" "Close to You") ("Mozart" "Eine Kleine Nachtmusik" (K 525)) ("Rolling Stones" "Brown Sugar") ("Tokens" "The Lion Sleeps Tonight") [change_begin] X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] [Function] merge result-type sequence1 sequence2 predicate &key :key The sequences sequence1 and sequence2 are destructively merged according to an order determined by the predicate. The result is a sequence of type result-type, which must be a subtype of sequence, as for the function coerce. The predicate should take two arguments and return non-nil if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the predicate should return nil. The merge function determines the relationship between two elements by giving keys extracted from the elements to the predicate. The :key function, when applied to an element, should return the key for that element; the :key function defaults to the identity function, thereby making the element itself be the key. The :key function should not have any side effects. A useful example of a :key function would be a component selector function for a defstruct structure, used to merge a sequence of structures. If the :key and predicate functions always return, then the merging operation will always terminate. The result of merging two sequences x and y is a new sequence z, such that the length of z is the sum of the lengths of x and y, and z contains all the elements of x and y. If x1 and x2 are two elements of x, and x1 precedes x2 in x, then x1 precedes x2 in z, and similarly for elements of y. In short, z is an interleaving of x and y. Moreover, if x and y were correctly sorted according to the predicate, then z will also be correctly sorted, as shown in this example. (merge 'list '(1 3 4 6 7) '(2 5 8) #'<) => (1 2 3 4 5 6 7 8) If x or y is not so sorted then z will not be sorted, but will nevertheless be an interleaving of x and y. The merging operation is guaranteed stable; if two or more elements are considered equal by the predicate, then the elements from sequence1 will precede those from sequence2 in the result. (The predicate is assumed to consider two elements x and y to be equal if (funcall predicate x y) and (funcall predicate y x) are both false.) For example: (merge 'string "BOY" "nosy" #'char-lessp) => "BnOosYy" The result can not be "BnoOsYy", "BnOosyY", or "BnoOsyY". The function char-lessp ignores case, and so considers the characters Y and y to be equal, for example; the stability property then guarantees that the character from the first argument (Y) must precede the one from the second argument (y). [change_begin] X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH) to specify that merge should signal an error if the sequence type specifies the number of elements and the sum of the lengths of the two sequence arguments is different. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9. [change_end] -------------------------------------------------------------------------------